{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 12.3 Insertion and deletion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.3-1\n",
    "\n",
    "> Give a recursive version of the TREE-INSERT procedure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.parent = None\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        if left is not None:\n",
    "            left.parent = self\n",
    "        if right is not None:\n",
    "            right.parent = self\n",
    "\n",
    "\n",
    "def insert(root, x):\n",
    "    if root is None:\n",
    "        return TreeNode(x)\n",
    "    if root.val > x:\n",
    "        root.left = insert(root.left, x)\n",
    "        root.left.parent = root\n",
    "    elif root.val < x:\n",
    "        root.right = insert(root.right, x)\n",
    "        root.right.parent = root\n",
    "    return root"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.3-2\n",
    "\n",
    "> Suppose that we construct a binary search tree by repeatedly inserting distinct values into the tree. Argue that the number of nodes examined in searching for a value in the tree is one plus the number of nodes examined when the value was first inserted into the tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Obviously"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.3-3\n",
    "\n",
    "> We can sort a given set of $n$ numbers by first building a binary search tree containing these numbers (using TREE-INSERT repeatedly to insert the numbers one by one) and then printing the numbers by an inorder tree walk. What are the worstcase and best-case running times for this sorting algorithm?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Worst: chain, $O(n^2)$.\n",
    "\n",
    "Best: $\\Theta(n \\lg n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.3-4\n",
    "\n",
    "> Is the operation of deletion \"commutative\" in the sense that deleting $x$ and then $y$ from a binary search tree leaves the same tree as deleting $y$ and then $x$? Argue why it is or give a counterexample."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No.\n",
    "\n",
    "![](img/12.3-4_1.png)\n",
    "\n",
    "Delete 0 then delete 1:\n",
    "\n",
    "![](img/12.3-4_2.png)\n",
    "![](img/12.3-4_3.png)\n",
    "\n",
    "Delete 1 then delete 0:\n",
    "\n",
    "![](img/12.3-4_4.png)\n",
    "![](img/12.3-4_5.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.3-5\n",
    "\n",
    "> Suppose that instead of each node $x$ keeping the attribute $x.p$, pointing to $x$'s parent, it keeps $x.succ$, pointing to $x$'s successor. Give pseudocode for SEARCH, INSERT, and DELETE on a binary search tree $T$ using this representation. These procedures should operate in time $O(h)$, where $h$ is the height of the tree $T$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In SEARCH and INSERT, we do not need to know the parent of $x$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_parent(root, node):\n",
    "    if node is None:\n",
    "        return None\n",
    "    a = tree_successor(tree_maximum(node))\n",
    "    if a is None:\n",
    "        a = root\n",
    "    else:\n",
    "        if a.left == node:\n",
    "            return a\n",
    "        a = a.left\n",
    "    while a is not None and a.right != node:\n",
    "        a = a.right\n",
    "    return a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Therefore we can find $x$'s parent in $O(h)$, DELETE is $O(h + h) = O(h)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 12.3-6\n",
    "\n",
    "> When node $z$ in TREE-DELETE has two children, we could choose node $y$ as its predecessor rather than its successor. What other changes to TREE-DELETE would be necessary if we did so? Some have argued that a fair strategy, giving equal priority to predecessor and successor, yields better empirical performance. How might TREE-DELETE be changed to implement such a fair strategy?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Randomly choose predecessor and successor."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
